package mo.offer_special;

import java.util.*;

public class L115 {

    //nums要是唯一的 最短 超序列
    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        int[] degree = new int[nums.length];
        Map<Integer, Set<Integer>> path = new HashMap<>();
        for (int[] sequence : sequences) {

            for (int i = 0; i+1 < sequence.length; i++) {
                int cur = sequence[i];
                int next = sequence[i+1];
                Set<Integer> nodes = path.getOrDefault(cur, new HashSet<>());
                if (!nodes.contains(next)) {
                    degree[next-1]++;
                }
                nodes.add(next);
                path.put(cur, nodes);
            }
        }

        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < degree.length; i++) {
            if (degree[i] == 0) {
                queue.offer(i+1);
            }
        }
        if (queue.size() != 1) {
            return false;
        }

        while (!queue.isEmpty()) {
            int from = queue.poll();
            Set<Integer> to = path.get(from);
            if (Objects.nonNull(to)) {
                for (int node : to) {
                    degree[node-1]--;
                    if (degree[node-1] == 0) {
                        queue.offer(node);
                    }
                }
            }
            if (queue.size() > 1) {
                return false;
            }
        }

        return true;
    }


    public static void main(String[] args) {
        //[]
        //[[],[]]
        L115 test = new L115();
        System.out.println(test.sequenceReconstruction(new int[]{4,1,5,2,6,3}, new int[][]{{5,2,6,3}, {4,1,5,2}}));
    }
}
